#include <vector>

#include "PriorityQueue.h"
#include "Key.h"
#include "Object.h"
#include "BlackHole.h"
#include "Gangster.h"
#include "Wall.h"
#include "Bullet.h"
#include "Cell.h"

using std::swap;

Priority assignKey( int& i ) {
    if( i == 1 ) return BOTTOM;
    if( i == 2 ) return LOW;
    if( i == 3 ) return MEDIUM;
    if( i == 4 ) return HIGH;
    if( i == 5 ) return PRIMARY;
    return BOTTOM;
}

Priority assignKey( Object* o ) {
    if( o == 0 ) return BOTTOM;
    switch( o->getSymbol() ) {
        case( Bullet::BULLETCHAR ):       return PRIMARY;
        case( BlackHole::BLACKHOLECHAR ): return HIGH;
        case( Gangster::GANGSTERCHAR ):
            if( o->isPlayer() )           return VERYLOW;
            else                          return MEDIUM;
        case( Wall::WALLCHAR ):
            if( o->getUpdateStatus() )    return LOW;
            else                          return BOTTOM;
        default:                          return BOTTOM;
    }
}

int parent( int i ) { return ( (i - 1) / 2 ); }

int left( int i ) { return (2 * i + 1); }

int right( int i ) { return (2 * i + 2); }

template<class T>
int max( vector<T>& ar, int a, int b ) {
    if( ar[a] > ar[b] ) return a;
    else return b;
}

template<class T>
void build_heap( vector<T>& ar, int N ) {
    for( int j = N/2; j >= 0; j-- ){
        heapify( ar, j, N );
    }
}

template<class T>
void heapify( vector<T>& ar, int i, int N ) {
    if( left( i ) >= N ){
        #ifdef DEBUG
            cout << "left( i ) = " << left(i) << " N" << endl;
        #endif
        return;
    }

    if( right( i ) >= N ){

        #ifdef DEBUG
            cout << "right( i ) = " << right(i) << " > N" << endl;
        #endif

        if( ar[ left(i) ] > ar[i] ) swap<T>( ar[i], ar[ left(i) ] );
        return;
    }

    if( ar[ max(ar, left(i), right(i) ) ] > ar[i] ){
        int a = max( ar, left(i), right(i) );

        #ifdef DEBUG
            cout << "ar[ " << max(ar, left(i), right(i) ) << " ] = ar[ max(ar, left(i), right(i) ) > " << "ar[i] == " << ar[i] << endl;
        #endif

        swap<T>( ar[i], ar[ max( ar, left(i), right(i) ) ] );

        #ifdef DEBUG
            cout << "heapify called on a = " << a << endl;
        #endif

        heapify<T>( ar, a, N );
    }
}

template<class T>
void Heapsort( vector<T>& ar, int N ) {
    build_heap<T>( ar, N );
    for( int i = N - 1; i >= 0; i-- ){
        swap( ar[0] , ar[i] );
        heapify( ar, 0, i );
    }
}

template<class T>
void PriorityQueue<T>::insert( T data ) {
    Key<T> key( data, assignKey( data ) );
    queue.push_back( key );
    int i = queue.size() - 1;
    for( ; i > 0 && queue[parent( i )] < key ; i = parent( i ) ) {
        queue[i] = queue[parent( i )];
    }
    queue[i] = key;
}

template<class T>
T PriorityQueue<T>::extractMax() {
    if( queue.size() > 0 ) {
        T max = queue.front().getData();
        queue[0] = queue[queue.size() - 1];
        queue.pop_back();
        heapify( queue, 0, queue.size() );
        return max;
    }
}

template<class T>
T PriorityQueue<T>::max() {
    if( queue.size() > 0 ) {
        return queue[0].getData();
    }
}

template class PriorityQueue<Object*>;
template void Heapsort<Cell>( vector<Cell>& ar, int N );
